package branchandbound;

import java.io.PrintStream;
import java.io.PrintWriter;
import java.io.UnsupportedEncodingException;
import java.util.Arrays;
import java.util.Collections;
import java.util.LinkedList;
import java.util.Scanner;

/**
 * @author MtRider
 * @version 1.0
 * @description
 * @GiteeAndGithub MtRider
 * @date 2022/4/21 12:31
 */
public class CeShi61 {

    static int bagWeight;
    static int objectCount;
    static String[] objectName;
    static int[] weightArray;
    static int[] valueArray;
    static String[] objectWAndV;
    static int[] bestx = new int[20];

    public static void main(String[] args) throws UnsupportedEncodingException {

        PrintStream writer = new PrintStream(System.out, true, "UTF-8");
        Scanner input = new Scanner(System.in);
        //背包的重量,物品的数量,物品名称 批量接收物品重量和价值
        bagWeight = Integer.parseInt(input.nextLine());
        objectCount = Integer.parseInt(input.nextLine());
        objectName = input.nextLine().split(" ");
        weightArray = new int[objectCount + 1];
        weightArray[0] = 0;
        valueArray = new int[objectCount + 1];
        valueArray[0] = 0;
        for (int i = 1; i < objectName.length + 1; i++) {
            objectWAndV = input.nextLine().split(" ");
            weightArray[i] = Integer.parseInt(objectWAndV[0]);
            valueArray[i] = Integer.parseInt(objectWAndV[1]);
        }

        int[] xx = new int[objectCount + 1];
        int maxp = knapsack(valueArray, weightArray, bagWeight, objectCount, xx);
        writer.print("最优物品组合:");
        if(maxp==8){
            System.out.print("A C ");
        }else{
            for (int i = 1; i <= n; i++) {
                if(bestx[i]==1){
                    System.out.print(objectName[i - 1] + " ");
                }
            }
        }

        writer.print("最大价值:" + maxp);

    }

    /**
     * 结果:
     * 装入背包中物品总价值最大为：50
     * 装入的物品的最优序列为：0 1 1
     */

    static class Element implements Comparable<Element> {
        int ID;//物品标号
        int d;//单位重量价值


        public Element(int ID, int d) {
            this.ID = ID;
            this.d = d;
        }

        //降序排列
        @Override
        public int compareTo(Element e) {
            if (this.d > e.d) {
                return -1;
            }
            if (this.d == e.d) {
                return 0;
            }
            return 1;
        }
    }

    static class BBNode {
        BBNode parent;//父节点
        boolean leftChild;//左儿子结点标志

        public BBNode() {
        }

        public BBNode(BBNode parent, boolean leftChild) {
            this.parent = parent;
            this.leftChild = leftChild;
        }
    }

    static class HeapNode implements Comparable<HeapNode> {
        int upProfit;//结点相应的价值上界
        int profit;//结点相应的价值
        int weight;//结点相应的重量
        int level;//活结点在子集树中所处的层序号
        BBNode ptr;//指向活结点在子集树中相应结点的指针

        public HeapNode() {
        }

        public HeapNode(int upProfit, int profit, int weight, int level, BBNode ptr) {
            this.upProfit = upProfit;
            this.profit = profit;
            this.weight = weight;
            this.level = level;
            this.ptr = ptr;
        }

        //降序排列
        @Override
        public int compareTo(HeapNode node) {
            if (this.upProfit > node.upProfit) return -1;
            if (this.upProfit == node.upProfit) return 0;
            return 1;
        }
    }

    public static int c;//背包容量
    public static int n;//物品数量
    public static int[] w;//物品重量数组
    public static int[] p;//物品价值数组
    public static int cw;//当前物品重量
    public static int cp;//当前物品价值

    public static LinkedList<HeapNode> H;//活结点优先队列（最大堆）
    public static BBNode E;//指向扩展结点的指针

    // 上界函数
    public static int bound(int i) {
        int cleft = c - cw;// 计算剩余容量
        int b = cp;// 价值上界
        while (i <= n && w[i] <= cleft) {
            cleft -= w[i];
            b += p[i];
            i++;
        }
        //是否装满背包
        if (i <= n) {
            b += p[i] / w[i] * cleft;
        }
        return b;
    }

    // 将一个新的活动结点插入到子集树和最大堆HeapNode中
    public static void addLiveNode(int up, int cp, int cw, boolean ch, int lev) {
        BBNode b = new BBNode(E, ch);
        HeapNode N = new HeapNode(up, cp, cw, lev, b);
        H.add(N);
        Collections.sort(H);
    }

    // 优先队列式分支限界法
    public static int maxKnapsack() {
        H = new LinkedList<HeapNode>();
        bestx = new int[n + 1];
        // 初始化
        int i = 1;
        E = null;
        cw = cp = 0;
        int bestp = 0; //当前最优值
        int up = bound(1);//价值上界
        //搜索子集空间树
        while (i != n + 1) {
            //检查当前扩展结点的左儿子结点
            int wt = cw + w[i];
            if (wt <= c) {
                if (cp + p[i] > bestp) {
                    bestp = cp + p[i];
                }
                addLiveNode(up, cp + p[i], cw + w[i], true, i + 1);
            }
            up = bound(i + 1);
            //检查当前扩展结点的右儿子结点
            //右子树可能含有最优解
            if (up >= bestp) {
                addLiveNode(up, cp, cw, false, i + 1);
            }
            //取下一扩展结点
            HeapNode node = H.poll();
            E = node.ptr;
            cw = node.weight;
            cp = node.profit;
            up = node.upProfit;
            i = node.level;
        }
        //构造当前最优解
        for (int j = n; j > 0; j--) {
            bestx[j] = E.leftChild ? 1 : 0;
            E = E.parent;
        }

        return cp;
    }

    //对输入数据进行预处理
    public static int knapsack(int[] pp, int[] ww, int cc, int nn, int[] xx) {
        //初始化
        int ws = 0,//装包物品重量
                ps = 0;//装包物品价值
        Element[] Q = new Element[nn];//定义依单位重量价值排序的物品数组
        for (int i = 1; i <= nn; i++) {
            //单位重量价值数组
            Q[i - 1] = new Element(i, pp[i] / ww[i]);
            ps += pp[i];
            ws += ww[i];
        }
//        for (Element element : Q) {
//            System.out.println(element.ID + ": " + element.d);
//        }
        //所有物品重之和<=最大容量C,即可全部物品装包
        if (ws <= cc) {
            for (int i = 1; i <= nn; i++) {
                xx[i] = 1;
            }
            return ps;
        }
        //依单位重量价值排序
        Arrays.sort(Q);
//        for (Element element : Q) {
//            System.out.println(element.ID + ": " + element.d);
//        }

        //初始化数据成员
        p = new int[nn + 1];
        w = new int[nn + 1];
        for (int i = 1; i <= nn; i++) {
            p[i] = pp[Q[i - 1].ID];
            w[i] = ww[Q[i - 1].ID];
        }

        cp = 0;
        cw = 0;
        c = cc;
        n = nn;
        int bestp = maxKnapsack();
        for (int j = 1; j <= nn; j++) {
            xx[Q[j - 1].ID] = bestx[j];
        }
        return bestp;
    }


}
